package org.basis.algorithm.sort;

import org.basis.algorithm.sort.common.SortUtil;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * 二分查找（二分查找在绝大多数情况下需要数组有序）
 *
 * @author Mr_wenpan@163.com 2022/02/14 12:39
 */
public class BinarySearch {

    public static void main(String[] args) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        while (!queue.isEmpty()) {
            Integer integer = queue.pollFirst();
            System.out.println(integer);
        }
        final int target = 22;
        int[] arr = SortUtil.generateRandomArray(100, 100);
        Arrays.sort(arr);
        int greaterThan = findGreaterThan(arr, target);
        SortUtil.printArr(arr);
        System.out.println("数组长度为：" + arr.length);
        if (greaterThan < arr.length) {
            System.out.println("第一个比 [ " + target + " ] 大的数是" + arr[greaterThan]);
        } else {
            System.out.println("大于边界，下标为：" + greaterThan);
        }

    }

    /**
     * 从arr数组中查找是否存在和target相等的数
     */
    public static int find(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) {
                return arr[mid];
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        // -1表示没有找到相等的数
        return -1;
    }

    /**
     * 从arr数组中查找第一个大于target的数的下标，如果不存在，则返回target数应该放置的位置
     */
    public static int findGreaterThan(int[] arr, int target) {
        int l = 0;
        int r = arr.length - 1;

        // 这里取等
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 找到了相等的数，则直接返回下标 + 1
            if (arr[mid] == target) {
                return mid + 1;
            } else if (arr[mid] > target) {
                r = mid - 1;
            } else {
                // 如果中点位置的数小于target
                l = mid + 1;
            }
        }

        // 最后返回(如果要求第一个比target大的数，则返回左边l，反之返回右边r)
        return l;
    }
}
